package com.leetcode.problems1044;


import java.util.*;

/**
 * https://leetcode-cn.com/problems/longest-duplicate-substring/
 * @Date 2021/12/23 09:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {


    public String longestDupSubstring(String s) {
        if(s == null || s.length() <= 1){
            return "";
        }
        int l = 1;
        int r = s.length() - 1;
        int start = -1;
        int len = 0;
        while(l <= r){
            int m = (r - l) / 2 + l;
            int ret = search(s,m);
            if(ret == -1){
                r = m - 1;
            }else{
                l = m + 1;
                start = ret;
                len = m;
            }
        }
        return start == - 1 ? "" : s.substring(start,start + len);
    }

    /**
     * 在字符串s中查找，len长度的重复子串，如果没有返回 -1，有：返回开始下标
     * @param s
     * @param j
     * @return
     */
    public int search(String s,int j){
        Set<String> contains = new HashSet<>();
        for (int i = 0; i + j <= s.length(); i++) {
            if (!contains.add(s.substring(i,i+j))) {
                return i;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        String str = "avdfc";
        System.out.println(new Solution().longestDupSubstring(str));
    }
}
